/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *																 *
 *	r2GL - r2 Graphs Library									 *
 *																 *
 *	File:		Graph.h											 *
 *	Authors:	Rafael Kikuchi ( shinjikik@gmail.com )			 *
 *				Rafael Romeiro ( rafaelromeiro@gmail.com )		 *
 *	Date:		08/09/2008										 *
 *	License:	CC-GNU LGPL										 *
 *				http://creativecommons.org/licenses/LGPL/2.1/	 *
 *	Version:	0.1.0											 *
 *																 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <math.h>
#include <queue>

#include "Node.h"

#define r2MATRIX 0
#define r2LIST 1
#define r2UNDIRECTED 0
#define r2DIRECTED 1
#define r2UNWEIGHTED 0
#define r2WEIGHTED 1
#define r2INFINITY (3.4f * pow(10.0f, 38))

using namespace std;

namespace r2GL
{

class Graph
{
public:
	Graph (void);
	Graph (const char *FileInput, bool Directed = r2DIRECTED, int StructType = r2MATRIX);

	Graph &operator=(const Graph &g);

	void WriteGraph (const char *FileOutput);
	void WriteInfo (const char *FileOutput);
	void RefreshNodeDegree (int node);
	int GetNumNodes (void);
	int GetNodeDegree (int node);

	void BFS (int root, bool ResetMarks = true, int MarkAs = 1, bool UseMark2 = false);
	void DFS (int root);
	bool HasCycle (void);

	void WriteBFSTree (const char *FileOutput, int root);
	void WriteDFSTree (const char *FileOutput, int root);

	void RefreshComponents (void);
	void WriteConnComponents (const char *FileOutput);
	void Reverse (void);

	void WriteCycle (const char *FileOutput);

	int GetMemSize (void);

	void GetDistances (int root, vector<float> &distances);
	void GetDistances (int root, vector<vector<int>> &paths, vector<float> &distances);
	void Dijkstra (int root);
	float Prim (int root);
	void WriteMST (const char *FileOutput);
	float GetMeanDistance (void);
	float GetDiameter (void);
	void GetMeanDistanceAndDiameter (vector<float> &results);

protected:
	void HasCycleVisit (int node, bool &hasCycle);
	void AllocateInMemory();

	bool isDirected, isWeighted, dirtyComponents, hasNegative;
	int structureType, numNodes, numEdges;

	vector<vector<bool>> adjMatrix;
	vector<vector<int>> adjList;

	vector<vector<float>> WeightMatrix;

	vector<int> cycle;
	vector<vector<int>> components;
	vector<Node> nodes;
};

} //namespace

#endif